/*
* 二叉平衡树 Adelson-Velsky-Landis Tree
* 带头节点
*/

#pragma once
#include<assert.h>

template<typename T>
class AvlNode
{
public:
	AvlNode(const T& _key)
		:key(_key), left(nullptr), parent(nullptr), right(nullptr), balance(0) {}

	AvlNode<T>* BuyNode(const T& key)
	{
		AvlNode<T>* newNode = new AvlNode<T>(key);
		assert(nullptr != newNode);
		return newNode;
	}
	void FreeNode(AvlNode<T>* node)
	{
		delete node;
		node = nullptr;
	}
public:
	AvlNode<T>* left;
	AvlNode<T>* parent;
	AvlNode<T>* right;
	int balance; // -1, 1, 0
	T key;
};

template<typename T>
class AvlTree
{
public:
	AvlTree();
	~AvlTree();

	void InOrder();
	void NoRecInOrder();
	void MirrorNoRecInOrder();

	bool Insert(const T& key);
	bool Delete(const T& key);

	AvlNode<T>* FindValue(const T& key);
	AvlNode<T>* NoRecFindValue(const T& key);

	int GetSize();
	AvlNode<T>* GetHead();
	bool IsEmpty();
	bool Is_BSTTree(AvlNode<T>* root);
	bool Is_AVLTree(AvlNode<T>* root);
private:
	void _InOrder(AvlNode<T>* root);
	AvlNode<T>* _FindValue(AvlNode<T>* root, const T& key);
	AvlNode<T>* NextNode(AvlNode<T>* node);
	AvlNode<T>* PreNode(AvlNode<T>* node);
	void RotateLeft(AvlNode<T>* node);
	void RotateRight(AvlNode<T>* node);
	void LeftBalance(AvlNode<T>* node);
	void RightBalance(AvlNode<T>* node);
	void AdjustTree(AvlNode<T>* node);
	int DepthOfBinaryTree(AvlNode<T>* root);

private:
	AvlNode<T>* head;
	int cursize;
};